/**
给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。 
数据范围： 1 \le |str1|,|str2| \le 50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n^2)O(n 2 )，时间复杂度 O(n^2)O(n 2 )
示例1:
输入："1AB2345CD","12345EF"
返回："234"
*/

/**
这条一开始我的思路被固化了，想要dp[i][j]存储i，j对应最大的公共子串的长度，
其实不需要，因为有 maxLength 和 lastIndex
*/
import java.util.*;
public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
     public static String LCS (String str1, String str2) {
         
            int[][] dp=new int[str1.length()][str2.length()];
            int maxLength = 0;
            int lastIndex = 0;
            char[] st1=str1.toCharArray();
            char[] st2=str2.toCharArray();
            for(int i=0;i<st1.length;i++){
                for(int j=0;j<st2.length;j++){
                    if(st1[i]==st2[j]){
                        if(i==0 || j==0){ //这个if是个精髓，节省很多代码
                            dp[i][j]=1;
                        }else{
                            dp[i][j]=dp[i-1][j-1]+1;
                        }
                    }
                    if (dp[i][j]>maxLength){
                        maxLength=dp[i][j];
                        lastIndex=j;
                    }
                }
            }

            return str2.substring(lastIndex-maxLength+1,lastIndex+1);
        }
}